package com.fw.leetcode.binarysearch;

import com.fw.leetcode.LeetCode;

/**
 * 268. Missing Number
 *
 * Given an array nums containing n distinct numbers in the range [0, n],
 * return the only number in the range that is missing from the array.
 *
 * Example 1:
 *  Input: nums = [3,0,1]
 *  Output: 2
 *  Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3].
 *               2 is the missing number in the range since it does not appear in nums.
 *
 * Example 2:
 *  Input: nums = [0,1]
 *  Output: 2
 *  Explanation: n = 2 since there are 2 numbers, so all numbers are in the range [0,2].
 *               2 is the missing number in the range since it does not appear in nums.
 *
 * Example 3:
 *  Input: nums = [9,6,4,2,3,5,7,0,1]
 *  Output: 8
 *  Explanation: n = 9 since there are 9 numbers, so all numbers are in the range [0,9].
 *               8 is the missing number in the range since it does not appear in nums.
 *
 * Constraints:
 *  n == nums.length
 *  1 <= n <= 10^4
 *  0 <= nums[i] <= n
 *  All the numbers of nums are unique.
 *
 * Follow up: Could you implement a solution using only O(1) extra space complexity and O(n) runtime complexity?
 */
public class Num_0268 implements LeetCode {

    private interface Solution {
        int missingNumber(int[] nums);

        default void assertExpected(int[] nums, int expected) {
            if (missingNumber(nums) != expected) {
                missingNumber(nums);
            }
        }
    }

    private static class BinarySearchSolution implements Solution {
        public int missingNumber(int[] nums) { // 很慢，占内存高，时O(nlog n)+O(log n) 空O(1)，不满足要求时O(n)空O(1)
            // 冒泡 + 二分
            // 1.冒泡：从左往右，升序排，每轮依次从 0 起至 end-i 处，将`最大值`放最后
            //     或 从左往右，升序排，每轮依次从 i 起至 end，将`最小值`放最前
            int tmp;
            for (int i = 0; i < nums.length - 1; i++) {
                for (int j = 0; j < nums.length - 1 - i; j++) {
                    if (nums[j] > nums[j + 1]) {
                        tmp = nums[j + 1];
                        nums[j + 1] = nums[j];
                        nums[j] = tmp;
                    }
                }
            }
            // 2.二分
            // array = [0, 1, 2, 3, 5, 6, 7], length=7
            // index =  0  1  2  3  4  5  6  => 从索引 4 开始向后都偏移 1
            // 目标：找到第一个索引和值不同的位置，即所求
            // 特殊边界点：最后一个值不满足索引和值偏移
            // - [0,1] => 2
            //    0 1
            if (nums.length != nums[nums.length - 1]) return nums.length;
            int left = 0;
            int right = nums.length - 1;
            int mid;
            int maybe = -1;
            while (left <= right) {
                mid = (left + right) / 2;
                if (nums[mid] != mid) { // mid 可能值大了，往前找试试
                    maybe = mid;
                    right = mid - 1;
                } else { // 索引和值相等，则小了，需往后找
                    left = mid + 1;
                }
            }
            return maybe;
        }
    }

    private static class BitMapSolution implements Solution {
        static final short[] bit_to_one = new short[]{
                0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80
        }; // use `|`

        public int missingNumber(int[] nums) { // 位图，两次遍历，时O(n) 空O(n)，不满足要求时O(n)空O(1)
            // 分配位图
            // 3个 => 1B 3bit 剩余 5bit 填充1
            // 8个 => 1B 8bit
            // 9个 => 2B 9bit 剩余 7bit 填充1
            short[] bitFlags = new short[((nums.length + 1) >> 3) + 1];
            for (int i = 0; i < nums.length; i++) {
                bitFlags[nums[i] >> 3] |= bit_to_one[nums[i] & 0x7];
            }
            for (int i = ((nums.length + 1) & 0x7); i < 8; i++) {
                bitFlags[bitFlags.length - 1] |= bit_to_one[i];
            }
            for (int j = 0; j < bitFlags.length; j++) {
                if ((bitFlags[j] ^ 0x00ff) > 0) { // 低 8bit 中存在 0 的位
                    int oneByte = bitFlags[j] ^ 0x00ff; // 0 的位变 1，其余位变 0
                    int k = 1;
                    for (; k < 8; k++) { // 探测 1 在第几位
                        if ((oneByte >> k) <= 0) {
                            break;
                        }
                    }
                    return (j << 3) + k - 1;
                }
            }
            return 0;
        }
    }

    private static class SumSolution implements Solution {
        public int missingNumber(int[] nums) { // 求总和计算差值，一次遍历，时O(n) 空O(1)，最优
            int n = nums.length;
            int remainTotal = n * (n + 1) / 2;
            for (int num : nums) {
                remainTotal -= num;
            }
            return remainTotal;
        }
    }

    public static void main(String[] args) {
        Solution solution = new SumSolution();
        solution.assertExpected(new int[]{3, 0, 1}, 2);
        solution.assertExpected(new int[]{0, 1}, 2);
        solution.assertExpected(new int[]{9, 6, 4, 2, 3, 5, 7, 0, 1}, 8);
        solution.assertExpected(new int[]{0, 2, 3}, 1);
    }
}
